package th.retrofit.lib;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Solution57 {

    public int[][] insert(int[][] intervals, int[] newInterval) {
        int length = intervals.length;
        int endIndex = 0;
        int beginIndex = 0;
        for (int[] interval : intervals) {
            if (newInterval[0] > interval[1]) {
                beginIndex++;
            } else {
                break;
            }
        }
        endIndex = beginIndex;
        for (int i = endIndex; i < length; i++) {
            if (newInterval[1] >= intervals[i][0]) {
                endIndex ++;
            } else {
                break;
            }
        }
        List<int[]> results;
        if(endIndex == 0) {
            results = new LinkedList<>();
            results.add(newInterval);
            results.addAll(Arrays.asList(intervals));
        } else if (beginIndex == length) {
            results = new LinkedList<>(Arrays.asList(intervals));
            results.add(newInterval);
        } else {
            if (beginIndex != endIndex) {
                newInterval[0] = Math.min(newInterval[0], intervals[beginIndex][0]);
                newInterval[1] = Math.max(newInterval[1], intervals[endIndex - 1][1]);
            }
            results = new LinkedList<>();
            for (int i = 0; i < beginIndex; i++) {
                results.add(intervals[i]);
            }
            results.add(newInterval);
            for (int i = endIndex; i < length; i++) {
                results.add(intervals[i]);
            }
        }
        int[][] arr = new int[results.size()][2];
        return results.toArray(arr);
    }

    public static void main(String[] args) {
        int[][] intervals = new int[][]{{6,7},{8,9}};
        int[] newInterval = new int[]{10, 11};
        intervals = new Solution57().insert(intervals, newInterval);
        for (int i = 0; i < intervals.length; i++) {
            for (int j = 0; j < 2; j++) {
                System.out.print(intervals[i][j]);
                System.out.print(", ");
            }
            System.out.println();
        }
    }

}
